/**
 * 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
 * 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
 * 合并必须从两个树的根节点开始。
 * 输入：    1               2
 *         / \             / \
 *        3   2           1   3
 *       /                \   \
 *      5                  4   7    
 * 输出：
 *          3
 *         / \
 *        4   5
 *       / \   \
 *      5   4   7
 */
#include<queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


/**
 * TIPS:二叉树递归遍历(先序、中序、后序三种) == 深度优先遍历DFS
 * 
 * 递归三步：
 * 1、确定递归函数的参数和返回值
 *    参数：两个二叉树根节点   返回值：合并后二叉树根节点
 * 2、确定终止条件
 *    因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了啊（如果t2也为NULL也无所谓，合并之后就是NULL）。
 *    反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。
 *    即 if (t1 == NULL) return t2; if (t2 == NULL) return t1; 
 * 3、确定单层递归的逻辑
 *    重复利用一下t1这个树，t1就是合并之后树的根节点。
 *    那么单层递归中，就要把两棵树的元素加到一起。t1->val += t2->val;
 *    t1->left = mergeTrees(t1->left, t2->left);
 *    t1->right = mergeTrees(t1->right, t2->right);
 *    return t1;
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 可以直接在第一棵树上修改，也可以重新定义一个树，根节点设为0
        // TreeNode* root = new TreeNode(0);
        // root->val = t1->val + t2->val;
        // root->left = mergeTrees(t1->left, t2->left);
        // root->right = mergeTrees(t1->right, t2->right)

        if(root1 == nullptr){
            return root2;
        }
        if(root2 == nullptr){
            return root1;
        }

        // 先序遍历
        root1->val += root2->val;                               // 根
        root1->left = mergeTrees(root1->left, root2->left);     // 左
        root1->right = mergeTrees(root1->right, root2->right);  // 右
        // 同理，调整顺序可得中序和后序遍历

        return root1;
    }
};

/**
 * TIPS:迭代法 == 层次遍历
 */
class Solution_2 {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空，val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空，加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空，加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 当t1的左节点 为空 t2左节点不为空，就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空，就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};